package com.li.suanfa;

import java.util.Arrays;
import java.util.Random;

/**  
* 类说明   
*  
* @author ****  
* @date 2018年4月1日  新建  
*/
public class HeapSort {
	public static final int SIZE = 10;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		System.out.println(Arrays.toString(array));
		heapSort(array,array.length);
		System.out.println(Arrays.toString(array));
	}
	public static void heapSort(int[] a,int n){
		int i,j,k;
		for(i=(n/2)-1;i>=0;i--){
			while(i*2+1<n){
				j = i*2+1;
				if(j+1<n){
					if(a[j+1]>a[j]){
						j++;
					}
				}
				if(a[j]>a[i]){
					swap(a,i,j);
					i = j;
				}else{
					break;
				}
			}
		}
		System.out.println("构成的初始堆:"+Arrays.toString(a));
		
		for(i=n-1;i>0;i--){
			swap(a,i,0);
			k=0;
			while(2*k+1<i){
				j=2*k+1;
				if((j+1)<i){
					if(a[j]<a[j+1]){
						j++;
					}
				}
				if(a[k]<a[j]){
					swap(a,j,k);
					k=j;
				}else{
					break;
				}
			}
		}
		
	}
	
	public static void swap(int[] array,int i,int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
  